package com.github.hgkmail.hello.leetcode101.dualpointer;

import java.util.HashMap;
import java.util.Map;

public class LC76MinimumWindowSubstring {
    public String minWindow(String s, String t) {
        //base case
        if (s.length()<=0 || t.length()<=0) {
            return "";
        }
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        //t字符串的统计信息 <字符，出现次数>
        Map<Character, Integer> need=new HashMap<>();
        //s子串的统计信息
        Map<Character, Integer> window=new HashMap<>();
        //统计
        for (int i = 0; i < tArr.length; i++) {
            need.put(tArr[i], need.getOrDefault(tArr[i], 0)+1);
        }

        int r=0; //先指针
        int l=0; //后指针
        int resL=0; //结果
        int resLen=sArr.length+1; //结果
        int distance=0; //指标
        while (r< sArr.length) {
            //更新指标
            char c=sArr[r];
            if (need.containsKey(c)) {  //有效字符种类
                window.put(c, window.getOrDefault(c, 0)+1);
                if (window.get(c)<=need.get(c)) { //有效字符频数
                    distance+=1;
                }
            }
            //判断后指针是否移动
            while(distance==tArr.length) {
                //更新结果
                if (resLen>r-l+1) {
                    resLen=r-l+1;
                    resL=l;
                }
                //移动后指针，并更新指标
                char d=sArr[l];
                if (need.containsKey(d)) {   //有效字符种类
                    window.put(d, window.getOrDefault(d, 0)-1);
                    if (window.get(d)<need.get(d)) {  //有效字符频数
                        distance-=1;
                    }
                }
                //后指针移动
                l+=1;
            }

            //先指针移动
            r+=1;
        }

        //是否真的找到了
        if (resLen>sArr.length) {
            return "";
        }
        return s.substring(resL, resL+resLen);
    }

    public static void main(String[] args) {
        System.out.println(new LC76MinimumWindowSubstring().minWindow("ADOBECODEBANC", "ABC"));
    }
}
